package leetcode_201_300;

import java.util.*;

public class LeeCode_207_timeout {
    public static void main(String[] args) {
        System.out.println(canFinish(2, new int[][]{{1, 0}}));
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }
    private static class Node{
        private int val;
        private List<Integer> next;
    }
    private static boolean canFinish(int numCourses, int[][] prerequisites) {
        Node[] ls = new Node[numCourses];
        for (int i = 0; i < ls.length; i++) {
            ls[i] = new Node();
            ls[i].val = i;
            ls[i].next = new ArrayList<>();
        }
        for (int[] p : prerequisites) {
            ls[p[0]].next.add(p[1]);
        }
        Set<Integer> glo = new HashSet<>();
        for (int[] p : prerequisites) {
            if (glo.contains(p[1]))
                continue;
            if (!dfs(ls, new HashSet<>(), p[0], glo)) {
                return false;
            }
        }
        return true;
    }
    private static boolean dfs(Node[] ls, Set<Integer> set, int now, Set<Integer> glo){
        if (glo.contains(now))
            return true;
        if (set.contains(now))
            return false;
        set.add(now);
        glo.add(now);
        Node nowN = ls[now];
        List<Integer> nexts = nowN.next;
        for (Integer next : nexts) {
            Set<Integer> newS = new HashSet<>(set);
            if (!dfs(ls, newS, next, glo))
                return false;
        }
        return true;
    }
}
